//
// Created by yy on 2025/5/14.
//
#include <bits/stdc++.h>

using namespace std;

//交换
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

//1.1插入排序 直接插入排序
void InsertSort(int A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {
        if (A[i] < A[i - 1]) {
            A[0] = A[i];
            for (j = i - 1; A[0] < A[j]; j--) {
                A[j + 1] = A[j];
            }
            A[j + 1] = A[0];
        }
    }
}

//1.2 希尔排序
void ShellSort(int A[], int n) {
    int d, i, j;
    for (d = n / 2; d >= 1; d /= 2) {
        for (i = d + 1; i <= n; i++) {
            if (A[i] < A[i - d]) {
                A[0] = A[i];
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d) {
                    A[j + d] = A[j];
                }
                A[j + d] = A[0];
            }
        }
    }
}

//2.1选择排序 直接选择排序（简单选择排序）
void SelectSort(int A[], int n) {
    for (int i = 1; i <= n - 1; i++) {
        int min = i;
        for (int j = i + 1; j <= n; j++) {
            if (A[j] < A[min]) {
                min = j;
            }
        }
        if (min != i) {
            swap(A[i], A[min]);
        }
    }
}

//2.2 堆排序
void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1]) {
            i++;
        }
        if (A[0] >= A[i]) {
            break;
        } else {
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

void BuildMaxHeap(int A[], int len) {
    for (int i = len / 2; i >= 1; i--) {
        HeadAdjust(A, i, len);
    }
}

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);
    for (int i = len; i >= 2; i--) {
        swap(A[i], A[1]);
        HeadAdjust(A, 1, i - 1);
    }
}

//3.1交换排序 冒泡排序
void BubbleSort(int A[], int n) {
    for (int i = 1; i <= n - 1; i++) {
        bool flag = false;
        for (int j = n; j > i; j--) {
            if (A[j] < A[j - 1]) {
                swap(A[j], A[j - 1]);
                flag = true;
            }
        }
        if (flag == false) {
            return;
        }
    }
}

//3.2 快速排序
int Partition(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) {
            high--;
        }
        A[low] = A[high];
        while (low < high && A[low] <= pivot) {
            low++;
        }
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);
        QuickSort(A, pivotpos + 1, high);
    }
}

//4 归并排序
int *B = (int *) malloc(11 * sizeof(int));

void Merge(int A[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) {
        B[k] = A[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (B[i] <= B[j]) {
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while (i <= mid) {
        A[k++] = B[i++];
    }
    while (j <= high) {
        A[k++] = B[j++];
    }
}

void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid + 1, high);
        Merge(A, low, mid, high);
    }
}

//5. 基数排序

//总结：不稳定：希尔、选择、快速、堆。 稳定：直接、冒泡、归并、基数

int main() {
    int A[11] = {0, 5, 3, 9, 7, 1, 6, 4, 2, 8, 0};
//    InsertSort(A, 10);
//    ShellSort(A, 10);
//    BubbleSort(A, 10);
//    QuickSort(A, 1, 10);
//    SelectSort(A, 10);
//    HeapSort(A, 10);
    MergeSort(A, 1, 10);

    cout << A;
}